package shuati;

import java.util.*;

/**
 * @author clear
 * @version 1.0
 * @description:
 * @date 2023/11/23 15:00
 */


class Node{
    int val;
    Node next;
    public Node(int val){
        this.val = val;
    }
}
public class Demo01 {



/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            int n = Integer.parseInt(in.nextLine());
            String[] arr = new String[n];
            for(int i = 0;i<n;i++){
                arr[i] = in.nextLine();
            }

            for(int i = 0;i<n-1;i++){
                if (arr[i].contains(",") || arr[i].contains(" ")){
                    System.out.print("\""+arr[i]+"\"");
                }else{
                    System.out.print(arr[i]);
                }
                System.out.print(", ");
            }
            if (arr[n-1].contains(",") || arr[n-1].contains(" ")){
                System.out.print("\""+arr[n-1]+"\"");
            }else{
                System.out.print(arr[n-1]);
            }



        }
    }*/





/*
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long[] arr = new long[81];
        fib(arr);

        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int f= in.nextInt();
            int t = in.nextInt();
            long sum = 0;
            for(int i = f;i<=t;i++){
                sum+=arr[i];
            }
            System.out.println(sum);
        }
    }

    private static void fib(long[] arr) {
        arr[1] = 1;
        arr[2] = 1;
        for(int i = 3;i<81;i++){
            arr[i] = arr[i-1]+arr[i-2];
        }
    }*/


   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String str = in.next();
            String str1 = in.next();

            int count = 0;
            for(int i = 0;i<str.length()-str1.length()+1;i++){
                if (str.charAt(i)==str1.charAt(0)){
                    int flag = 1;
                    for(int j = 0;j<str1.length();j++){
                        if (str.charAt(i+j) != str1.charAt(j)){
                            flag=0;
                            break;
                        }
                    }
                    if (flag==1){
                        count++;
                        i=i+str1.length()-1;
                    }
                }
            }
            System.out.println(count);


        }
    }*/









/*
    static int flag  = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] arr = new int[100001];

        fib(arr);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            if (n>= flag){
                System.out.printf("%06d",arr[n]);
            }else {
                System.out.println(arr[n]);
            }
        }
    }

    private static void fib(int[] arr) {
        arr[1] = 1;
        arr[0] = 1;
        for(int i = 2;i<100001;i++){
            arr[i] = arr[i-1]+arr[i-2];
            if (arr[i]>=1000000 && flag == 0){
                flag = 1;
            }
            arr[i]%=1000000;
        }

    }
*/



/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case


        }
    }*/


/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            List<Integer> list = new ArrayList<>();
            int n =a;
            for(int i = 2;i*i<=a;i++){
                while (a%i==0){
                    list.add(i);
                    a/=i;
                }
            }
            if (a!=1){
                list.add(a);
            }
            System.out.print(n+" = ");

            for(int i = 0;i< list.size()-1;i++){
                System.out.print(list.get(i)+" * ");
            }
            System.out.print(list.get(list.size()-1));


        }
    }*/

    private static boolean isS(int a) {
        for(int i = 2;i<a;i++) {
            if (a%i==0){
                return false;
            }
        }
        return true;
    }

 /*   public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
           int n = in.nextInt();
           int count = 0;
           for(int i = 2;i*i<=n;i++){
               if (n%i==0){
                   while (n%i==0){
                       n/=i;
                   }
                   count++;
               }
           }
           if (n!=1){
               count++;
           }
            System.out.println(count);


        }
    }*/


   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            HashSet<Integer> hash = new HashSet<>();
            while (n>2){
                int flag = 0;
                for(int i = 2;i<n;i++){
                    if (n%i==0){
                        n/=i;
                        hash.add(i);
                        flag = 1;
                        break;
                    }
                }
                if (flag==0){
                    hash.add(n);
                    break;
                }

            }
            if (n==2){
                System.out.println(1);
                continue;
            }
            System.out.println(hash.size());


        }
    }*/




   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String mi = in.nextLine();
            char[] arr = mi.toCharArray();
            StringBuilder sb = new StringBuilder();
            for(int i = 0;i<arr.length;i++){
                if (arr[i]>'E' && arr[i]!=' '){
                    sb.append((char) (arr[i]-5));
                }else if(arr[i]==' '){
                    sb.append(arr[i]);
                }else{
                    sb.append((char) ('Z'-(5-(arr[i]-'A'))));
                }
            }
            System.out.println(sb);


        }
    }

*/




/*
    public static void main(String[] args) {
        int[] arr = {3,2,5};
        System.out.println(getFirstUnFormedNum(arr));
    }*/
    /*public static  int getFirstUnFormedNum(int[] arr) {
        HashMap<Integer, Integer> hash = new HashMap<>();
        //排序
        Arrays.sort(arr);

        //求子集和
        int max = 0;
        for(int i = 0;i<arr.length;i++){
            max+=arr[i];
        }

        //求子集
        for(int i = 1;i<(1<<arr.length);i++){
            int tmp = 0;
            //判断那个比特为是1，是1就选上
            int[] isv = new int[32];
            int j = i;
            int k = 0;
            while (j>0){
                isv[k] = j&1;
                k++;
                j=j>>1;
            }

            for(int m=0;m<k;m++){
                if (isv[m]==1){
                    tmp+=arr[m];
                }
            }
            hash.put(tmp,1);

        }

        for(int i = arr[0];i<max;i++)
        {
            if (!hash.containsKey(i)){
                return i;
            }
        }

        return max+1;

    }
*/






   /* public static void main(String[] args) {
        System.out.println(countCompleteSubstrings("igigee" ,2));
    }
    public static  int countCompleteSubstrings(String word, int k) {
        //找子串
        int count = 0;
        if (k==1){
            count+=word.length();
        }

        HashMap<String,Integer> hashmap = new HashMap<>();
        for(int i = 0;i<word.length();i++){
            for(int j = 0;j<i;j++){
                String zic = word.substring(j, i+1);
                //遍历子串，看是否相邻是否大于2
                char[] arr = zic.toCharArray();
                int[] hash = new int[128];
                boolean flag = true;
                if (hashmap.containsKey(zic)){
                    count++;
                    continue;
                }



                hash[arr[0]]++;
                for(int a = 1;a<zic.length();a++){
                        if (Math.abs(arr[a]-arr[a-1])>2){
                            flag=false;
                            break;
                        }else{
                            //将每个字符放到哈希表中统计出现的次数
                            hash[arr[a]]++;
                            if (hash[arr[a]]>k){
                                flag = false;
                                break;
                            }
                        }
                    }
                if (!flag)continue;


                //遍历哈希表中的每个位置，是否都是k
                for(int m = 0;m<128;m++) {
                    if (hash[m] == 0 || hash[m] == k){
                        continue;
                    }else{
                        flag = false;
                        break;
                    }
                }
                if (!flag)continue;

                if (flag){
                    count++;
                    hashmap.put(zic,1);
//                    System.out.println(zic);
                }
            }
        }

        return count;

    }
*/
//    public int minimumAddedCoins(int[] coins, int target) {
//
//    }

/*    public List<Integer> findPeaks(int[] mountain) {
        int len = mountain.length;
        List<Integer> ret = new ArrayList<>();
        for(int i = 1;i<len-1;i++){
            if (mountain[i] > mountain[i-1] && mountain[i] > mountain[i+1]){
                ret.add(i);
            }
        }
        return ret;


    }*/


   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            if (n==0){
                break;
            }

            int count = 0;
            while (n>=2){
                n = (int) Math.ceil((double)n/3);
                count++;
            }
            System.out.println(count);


        }
    }*/







    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            if (n == 0){
                break;
            }
            int num = 1;
            while (n>0){
                n--;
                while (true){
                    if ((num-1)%5!=0){
                        break;
                    }
                    if ()
                    num++;
                }


            }


        }
    }
*/



    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        String nodeValue = in.nextLine();
        String[] nodes = nodeValue.split(" ");
        Node dummyHead = new Node(-1);
        Node tail = dummyHead;
        for(int i = 0;i<n;i++){
            //链表的尾插法
            Node node = new Node(Integer.parseInt(nodes[i]));
            tail.next = node;
            tail = node;
        }

        //获取区间范围
        String part = in.nextLine();
        int left = Integer.parseInt(part.split(" ")[0]);
        int right = Integer.parseInt(part.split(" ")[1]);

        Node newHead = reverPartList(dummyHead.next,left,right);

        while (newHead!=null){
            System.out.print(newHead.val+" ");
            newHead = newHead.next;
        }

    }

    private static Node reverPartList(Node head, int left, int right) {
        Node dummyHead = new Node(-1);
        dummyHead.next = head;
        Node prev = dummyHead;
        for(int i = 1;i<left;i++){
            prev = prev.next;
        }

        Node cur = prev.next;
        for(int i = left; i < right; i++){
            Node third = cur.next;
            cur.next = third.next;
            third.next = prev.next;
            prev.next = third;
        }

        return dummyHead.next;

    }
*/

/*    public int Add(int num1,int num2) {
        int a = num1;
        int b = num2;
        while (b!=0){
            int a1 = a^b;
            int b1 = a&b;
            a = a1;
            b = b1<<1;
        }

        return a;
    }*/





    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String a = in.next();
            String b = in.next();
            String c = in.next();
            BigDecimal aa = new BigDecimal(a);
            BigDecimal bb = new BigDecimal(b);
            BigDecimal cc = new BigDecimal(c);

            if (aa.add(bb).compareTo(cc)>0
                    && aa.add(cc).compareTo(bb)>0
                    && bb.add(aa).compareTo(cc)>0){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }




        }
    }*/







/*    public int jumpFloorII (int number) {
        return 1<<--number;
    }*/


  /*  public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String n = in.next();
            String r = in.next();

            BigDecimal r1 = new BigDecimal(r);
            BigDecimal pi = new BigDecimal("6.28");
            if ((r1.multiply(pi)).compareTo(new BigDecimal(n))==-1){
                System.out.println("No");
            }else {
                System.out.println("Yes");
            }

        }
    }
*/

 /*   public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int[] arr = new int[10001];
        fib(arr);

        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int[] ret = new int[n];
            StringBuilder a = new StringBuilder();
            for (int i = 0; i < n; i++) {
                ret[i] = in.nextInt();
                int tmp = arr[ret[i]];
                if (tmp<10){
                    a.append("000");
                    a.append(tmp);
                }else if(tmp<100){
                    a.append("00");
                    a.append(tmp);
                }else if(tmp < 1000){
                    a.append("0");
                    a.append(tmp);
                }else{
                    a.append(tmp);
                }
            }
            System.out.println(a.toString());
        }
    }

    private static void fib(int[] arr) {
        arr[1] = 1;
        arr[2] = 2;
        for (int i = 3; i <= 10000; i++) {
            arr[i] = (arr[i-1] + arr[i - 2]) % 10000;
        }
    }*/

}
/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
           String line = in.nextLine();
           while (line.length()>1) {
               int sum = 0;
               for(int i = 0;i<line.length();i++) {
                   sum += line.charAt(i)-'0';
               }
               line = String.valueOf(sum);
           }
            System.out.println(line);
        }
    }*/




/*    public int getMost(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        int[][] dp = new int[m+1][n+1];

        for(int i = 1;i<=m;i++){
            for(int j = 1;j<=n;j++){
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+board[i-1][j-1];
            }
        }

        return dp[m][n];



    }*/






    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int row = in.nextInt();
        int col = in.nextInt();
        int[][] mat = new int[row][col];
        int[][] book = new int[row][col];
        for(int i = 0;i<row;i++){
            for(int j = 0;j<col;j++){
                mat[i][j] = in.nextInt();
            }
        }
        ArrayList<Node> path = new ArrayList<>();
        ArrayList<Node> minPath = new ArrayList<>();

        getPath(mat,row,col,0,0,book,path,minPath);

        for(Node n:minPath){
            System.out.println("("+n.x+","+n.y+")");
        }


    }

    private static void getPath(int[][] mat,int row,int col,
            int x,int y,int[][] book,ArrayList<Node> path,ArrayList<Node> minPath) {

        //判断能否往下走
        if (x<0 || x>=row || y<0 || y>=col || book[x][y] == 1 || mat[x][y] == 1){
            return;
        }

        //将当前位置存到路径
        path.add(new Node(x,y));
        //标记当前位置
        book[x][y] = 1;
        //判断是否是出口
        if (x == row-1 && y == col-1){
            //一条新的路径产生，判断是否是更短的路径
            if (minPath.isEmpty() || path.size() < minPath.size()){
                //更新最短路径
                minPath.clear();
                for(Node n : path){
                    minPath.add(n);
                }
            }
        }
        //继续搜索上下左右四个方向
        getPath(mat,row,col,x+1,y,book,path,minPath);
        getPath(mat,row,col,x-1,y,book,path,minPath);
        getPath(mat,row,col,x,y+1,book,path,minPath);
        getPath(mat,row,col,x,y-1,book,path,minPath);

        //把当前位置从路径中删除
        path.remove(path.size()-1);
        book[x][y] = 0;



    }*/



/*    private static int[][] isv; //标记位
    private static int[] dx = {1,0,0,-1};
    private static int[] dy = {0,1,-1,0};
    private static List<List<Integer>> path;
    private static int m;
    private static int n;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);


        m = in.nextInt();
        n = in.nextInt();
        int[][] nums= new int[m][n];
        isv = new int[m][n];
        path = new ArrayList<>();

        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                nums[i][j] = in.nextInt();
            }
        }

        dfs(nums,0,0);

        System.out.println(path);


    }

    private static void dfs(int[][] nums, int x, int y) {
        List<Integer> tmp = new ArrayList<>();
        tmp.add(x);
        tmp.add(y);
        path.add(tmp);
        isv[x][y] = 1;

        if (nums[x][y]==0){
            for(int k = 0;k<4;k++){
                int dxx = x+dx[k];
                int dyy = y+dy[k];
                if (dxx>=0 && dxx<m && dyy >=0&&dyy<n && isv[dxx][dyy]==0){
                    dfs(nums,dxx,dyy);
                    path.remove(path.size() - 1);
                    isv[dxx][dyy] = 0;
                }

            }
        }


    }*/





   /* public int findNumberOfLIS(int[] nums) {
        int n = nums.length;

        int[] len = new int[n];
        int[] count = new int[n];
        for(int i = 0;i<n;i++){
            len[i]=count[i]=1;
        }
        int retlen = 1,retcount = 1;
        for(int i = 1;i<n;i++){
            for(int j = 0;j<i;j++){
                if (nums[j]<nums[i]){
                    if (len[j]+1==len[i]){
                        count[i] += count[j];
                    }else if(len[j]+1 > len[i]){
                        len[i] = len[j]+1;
                        count[i] = count[j];
                    }
                }

            }
            if (retlen == len[i]){
                retcount+=count[i];
            }
            else if(retlen <len[i]){
                retlen = len[i];
                retcount = count[i];
            }
        }
        return retcount;

    }*/


  /*  public int wiggleMaxLength(int[] nums) {
        //1.创建dp表
        //2.初始化
        //3.填表
        //4.返回值

        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        for(int i = 0;i<n;i++){
            f[i]=1;
            g[i]=1;
        }

        int ret = 1;
        for(int i = 1;i<n;i++){
            for(int j = 0;j<i;j++){
                if (nums[j]<nums[i]){
                    f[i] = Math.max(g[j]+1,f[i]);
                }else if(nums[j] > nums[i]){
                    g[i] = Math.max(f[j]+1,g[i]);
                }
            }
            ret = Math.max(ret,Math.max(f[i],g[i]));
        }
        return ret;



    }

*/




/*
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str1 = in.nextLine();
            String str2 = in.nextLine();

            List<String> list = new ArrayList<>();
            int is = 0;
            StringBuilder sb = new StringBuilder();
            for(int i = 0;i<str1.length();i++){
                if (str1.charAt(i) == ',' && is!=2){
                    sb.append(str1.charAt(i));
                    i++;
                    continue;
                }
                if (str1.charAt(i)=='"'){
                    is++;
                    if (is == 2){
                        list.add(sb.toString());
                        sb = new StringBuilder();
                        is =0;
                    }
                    continue;
                }else{
                    sb.append(str1.charAt(i));
                }


            }
            System.out.println(list);


        }
    }*/

    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int[] arr= new int[n];

            for(int i = 0;i<n;i++){
                arr[i] = i;
            }
            int mul = 1;
            for(int i = 0;i<n;i++){
                if (arr[i]==i){
                    mul = mul*((n-i-1)/(n-i));
                }else{
                    mul = mul*1;
                }
            }
            System.out.println(mul);


        }
    }
*/

   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long[] arr = new long[91];
        fib(arr);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            System.out.println(arr[n]);
        }
    }

    private static void fib(long[] arr) {
        arr[1] = 1L;
        arr[2] = 2L;
        for(int i = 3;i<=90;i++){
            arr[i] = arr[i-1]+arr[i-2];
        }
    }
*/


    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
           int n = Integer.parseInt(in.nextLine());
           String[] arr = new String[n];
           for(int i = 0;i<n;i++){
               arr[i] = in.nextLine();
           }
           StringBuffer ret = new StringBuffer();
           for(String tmp : arr){
               if (tmp.contains(", ") ||tmp.contains(",") || tmp.contains(" ")  ){
                   ret.append("\""+tmp+"\"");
               }else{
                   ret.append(tmp);
               }
               ret.append(", ");
           }
            System.out.println(ret.toString().substring(0, ret.length()-2));




        }
    }




*/




























